package com.nav.util;

import java.util.ArrayList;

public class MaxHeap<T extends Comparable<T>> implements Heap<T> {
	ArrayList<T> list = new ArrayList<T>();
	@Override
	public boolean add(T e) {
		list.add(e);
		int c = list.size() - 1, p = (c - 1) / 2;
		while(c > 0 && list.get(p).compareTo(e) < 0) {
			list.set(c, list.get(p));
			c = p;
			p = (c - 1) / 2;
		}
		list.set(c, e);
		return true;
	}

	@Override
	public T remove() {
		if(list.size() <= 0)
			return null;
		if(list.size() == 1)
			return list.remove(0);
		T e = list.remove(list.size() - 1);
		T r = list.set(0, e);
		int p = 0, c = (2 * p + 2 >= list.size() || list.get(2 * p + 1).compareTo(list.get(2 * p + 2)) >= 0) ? 2 * p + 1 : 2 * p + 2;
		while(c < list.size() && list.get(c).compareTo(e) > 0) {
			list.set(p, list.get(c));
			p = c;
			c = (2 * p + 2 >= list.size() || list.get(2 * p + 1).compareTo(list.get(2 * p + 2)) >= 0) ? 2 * p + 1 : 2 * p + 2;
		}
		list.set(p, e);
		return r;
	}
	
	@Override
	public T peek() {
		if(list.size() <= 0)
			return null;
		return list.get(0);
	}
}
